import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import util.PrintUtils;

public class MaxDui {

    private int[] arrays;
    private int size;

    public MaxDui(int[] source) {
        arrays = new int[source.length];
        size = arrays.length;
        System.arraycopy(source, 0, arrays, 0, source.length);
        for (int i = 0; i < arrays.length; i++) {
            up(i);
        }
    }

    public void up(int index) {
        if (index == 0) {
            return;
        }
        int parentIndex = (index - 1) >> 1;
        if (arrays[parentIndex] < arrays[index]) {
            swap(index, parentIndex);
            up(parentIndex);
        }
    }

    public void down(int index) {
        // 这里leftIndex 和 rightIndex 可能整型溢出
        int leftIndex = (index << 1) + 1, rightIndex = leftIndex + 1, minChildIndex = -1;
        if (leftIndex < size && arrays[leftIndex] > arrays[index]) {
            minChildIndex = leftIndex;
        }
        if (rightIndex < size && arrays[rightIndex] > arrays[leftIndex] && arrays[rightIndex] > arrays[index]) {
            minChildIndex = rightIndex;
        }
        if (minChildIndex > 0) {
            swap(index, minChildIndex);
            down(minChildIndex);
        }
    }

    private void swap(int i, int j) {
        int temp = arrays[i];
        arrays[i] = arrays[j];
        arrays[j] = temp;
    }

    private int remove() {
        if (size == 0) {
            throw new RuntimeException("空");
        }
        int val = arrays[0];
        arrays[0] = arrays[--size];
        down(0);
        return val;
    }

    public void print() {
        List<Integer> list = new ArrayList<>();
        while (size > 0) {
            list.add(remove());
        }
        System.out.println(list);
    }

    public static void main(String[] args) {
//        MaxDui model = new MaxDui(new int[] {4, 2,11, 4, 1, 5});
//        model.print();
        int[] array = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            array[i] = random.nextInt(100);
            int flag = random.nextInt(2);
            if (flag % 2 == 0) {
                //                System.out.println(model.remove());
            }
        }
        PrintUtils.arrayInt(array);
        new MaxDui(array).print();
    }
}
